home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / etc / lf / sort.cc < prev   
C/C++ Source or Header  |  1994-05-13  |  6KB  |  182 lines
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include <std.h>
  4.  
  5. /* the next 6 #defines implement a very fast in-line stack abstraction       */
  6.  
  7. #define MAX_STACK_SIZE 32
  8. #define DISPOSE_STACK(S) (free(S))
  9. #define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0)
  10. #define POP(LOW,HIGH)  do {LOW = (--top)->lo;HIGH = top->hi;} while (0)
  11. #define STACK_NOT_EMPTY (stack < top)                
  12. #define SWAP(A,B) do {char *_temp = (A);(A) = (B);(B) = _temp;} while (0)
  13.  
  14. /* Discontinue quicksort algorithm when partition gets below this size.
  15.    This particular magic number was chosen to work best on a Sun 4/260. */
  16. #define MAX_THRESH 30
  17.  
  18. /* Data structure for stack of unfulfilled obligations. */
  19. typedef struct 
  20. {
  21.   char **lo;
  22.   char **hi;
  23. } stack_node;
  24.  
  25. /* Once main array is partially sorted by quicksort the remainder is 
  26.    completely sorted using insertion sort, since this is efficient 
  27.    for partitions below MAX_THRESH size. BASE points to the beginning 
  28.    of the array to sort, and END_PTR points at the very last element in
  29.    the array (*not* one beyond it!). */
  30.  
  31. inline static void
  32. insert_sort (char **base_ptr, char **end_ptr)
  33. {
  34.   char **run_ptr;
  35.   char **tmp_ptr = base_ptr;
  36. #if defined (__GNUC__) && ! defined (__STRICT_ANSI__)
  37.   char **thresh  = end_ptr <? base_ptr + MAX_THRESH;
  38. #else
  39.   char **thresh  = base_ptr + MAX_THRESH;
  40.   if (thresh > end_ptr)
  41.     thresh = end_ptr;
  42. #endif
  43.  
  44.   /* Find the smallest element in the first threshold and put it at the 
  45.      end of the array.  This is guaranteed to be the smallest element in 
  46.      the array, and it speeds up the inner loop of insertion sort. */
  47.  
  48.   for (run_ptr = tmp_ptr + 1; run_ptr <= thresh; run_ptr++)
  49.     if (strcmp (*run_ptr, *tmp_ptr) < 0)
  50.       tmp_ptr = run_ptr;
  51.  
  52.   SWAP (*tmp_ptr, *base_ptr);
  53.  
  54.   /* Typical insertion sort, but we run from the `right-hand-side'
  55.      downto the `left-hand-side.' */
  56.  
  57.   for (run_ptr = base_ptr + 1; run_ptr < end_ptr; run_ptr++)
  58.     {
  59.       char *temp = *(tmp_ptr = run_ptr + 1);
  60.  
  61.       /* Select the correct location for the new element, 
  62.          by sliding everyone down by 1 to make room! */
  63.  
  64.       while (strcmp (temp, *--tmp_ptr) < 0)
  65.         tmp_ptr[1] = *tmp_ptr;
  66.  
  67.       tmp_ptr[1] = temp; 
  68.     }
  69. }
  70.  
  71. /* Return the median value selected from among the 
  72.    LOW, MIDDLE, and HIGH.  Rearrange LOW and HIGH so
  73.    the three values are sorted amongst themselves. 
  74.    This speeds up later work... */
  75.  
  76. inline static char *
  77. find_pivot (char **low, char **high)
  78. {
  79.   char **middle = low + ((high - low ) >> 1);
  80.  
  81.   if (strcmp (*middle, *low) < 0)
  82.     SWAP (*middle, *low);
  83.   if (strcmp (*high, *middle) < 0)
  84.     SWAP (*middle, *high);
  85.   else 
  86.     return *middle;
  87.  
  88.   if (strcmp (*middle, *low) < 0)
  89.     SWAP (*middle, *low);
  90.  
  91.   return *middle;
  92. }
  93.  
  94. /* Order elements using quicksort.  This implementation incorporates
  95.    4 optimizations discussed in Sedgewick:
  96.    
  97.    1. Non-recursive, using an explicit stack of log (n) pointers that 
  98.       indicate the next array partition to sort.
  99.  
  100.    2. Choses the pivot element to be the median-of-three, reducing
  101.       the probability of selecting a bad pivot value.
  102.  
  103.    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
  104.       insertion sort to sort within the partitions.  This is a
  105.       big win, since insertion sort is faster for small, mostly
  106.       sorted array segements.
  107.    
  108.    4. The larger of the 2 sub-partitions are always pushed onto the
  109.       stack first, with the algorithm then concentrating on the
  110.       smaller partition.  This *guarantees* no more than log (n)
  111.       stack size is needed! */
  112.       
  113. void
  114. sort (char **base_ptr, int total_elems)
  115. {
  116.   if (total_elems > MAX_THRESH)
  117.     {
  118.       char       **lo = base_ptr;
  119.       char       **hi = lo + (total_elems - 1);
  120.       char       **left_ptr;
  121.       char       **right_ptr;
  122.       stack_node   stack[MAX_STACK_SIZE];
  123.       stack_node  *top = stack + 1;
  124.  
  125.       while (STACK_NOT_EMPTY)
  126.         {
  127.           /* Select the median-of-three here. This allows us to
  128.             skip forward for the LEFT_PTR and RIGHT_PTR. */
  129.           char *pivot = find_pivot (lo, hi);
  130.           left_ptr  = lo + 1;
  131.           right_ptr = hi - 1; 
  132.  
  133.           /* Here's the famous ``collapse the walls'' section of
  134.             quicksort.  Gotta like those tight inner loops! */
  135.           do 
  136.             {
  137.               while (strcmp (*left_ptr, pivot) < 0)
  138.                 left_ptr++;
  139.  
  140.               while (strcmp (pivot, *right_ptr) < 0)
  141.                 right_ptr--;
  142.  
  143.               if (left_ptr < right_ptr) 
  144.                 {
  145.                   SWAP (*left_ptr, *right_ptr);
  146.                   left_ptr++;
  147.                   right_ptr--;
  148.                 }
  149.               else if (left_ptr == right_ptr) 
  150.                 {
  151.                   left_ptr++;
  152.                   right_ptr--;
  153.                   break;
  154.                 }
  155.             } 
  156.           while (left_ptr <= right_ptr);
  157.  
  158.           if ((right_ptr - lo) <= MAX_THRESH) 
  159.             {
  160.               if ((hi - left_ptr) <= MAX_THRESH) /* ignore both small tables */
  161.                 POP (lo, hi);
  162.               else              /* ignore small left table */
  163.                 lo = left_ptr;
  164.             }
  165.           else if ((hi - left_ptr) <= MAX_THRESH) /* ignore small right table */
  166.             hi = right_ptr;
  167.           else if ((right_ptr - lo) > (hi - left_ptr)) 
  168.             {                   /* push larger left table */
  169.               PUSH (lo, right_ptr);
  170.               lo = left_ptr;
  171.             }
  172.           else 
  173.             {                   /* push larger right table */
  174.               PUSH (left_ptr, hi);
  175.               hi = right_ptr;
  176.             }
  177.         }
  178.     }
  179.  
  180.   insert_sort (base_ptr, base_ptr + (total_elems - 1));
  181. }
  182.